package lastRemaining;

public class Solution {
    public int lastRemaining(int childrenNum , int count){
        if(0==childrenNum){
            return - 1;
        }
        int[] circle = new int[childrenNum];
        int idx = 0 ;
        int remainCount = childrenNum ;
        int tempCount = 0 ;
        while( remainCount > 1 ){
            if(circle[idx] != -1){
                if(tempCount++==(count-1)){
                    tempCount = 0 ;
                    remainCount-- ;
                    circle[idx] = -1 ;
                    System.out.println(idx + " out");
                }
            }

            idx = (idx + 1)%childrenNum ;
        }
        while(true){
            if(circle[idx] != -1){
                break;
            }
            idx = (idx + 1)%childrenNum ;
        }
        System.out.println(idx + " get gift");
        return idx ;
    }
    public int lastRemaining(Child head ,int count ){
        int rs = -1 ;
        if(null == head){
            return -1 ;
        }
        Child next = head ;
        int idx = count -1 ;
        do{
            if(next.getNext().getChildID() == next.getChildID()){
                System.out.println(next.getChildID()+" get kenan");
                rs = next.getChildID();
            }
            if(idx--==0){
                removeChild(next);
                idx = count -1;
            }
            System.out.println(idx+":"+next.getChildID());

        }while((next = next.getNext())!=null);
        return rs ;
    }
    public void removeChild(Child c){
        Child next = c.getNext();
        Child pre = c.getPre();
        next.setPre(pre);
        pre.setNext(next);
        System.out.println(c.getChildID() + " out ");
        c = null ;
    }
    public static void main(String[] args) {
        Child c0 = new Child(0);
        Child c1 = new Child(1);
        Child c2 = new Child(2);
        Child c3 = new Child(3);
        Child c4 = new Child(4);
        Child c5 = new Child(5);
        Child c6 = new Child(6);
        Child c7 = new Child(7);
        Child c8 = new Child(8);
        Child c9 = new Child(9);
        Child c10 = new Child(10);

        c0.setNext(c1);
        c1.setNext(c2);
        c2.setNext(c3);
        c3.setNext(c4);
        c4.setNext(c5);
        c5.setNext(c6);
        c6.setNext(c7);
        c7.setNext(c8);
        c8.setNext(c9);
        c9.setNext(c10);
        c10.setNext(c0);


        c0.setPre(c10);
        c10.setPre(c9);
        c9.setPre(c8);
        c8.setPre(c7);
        c7.setPre(c6);
        c6.setPre(c5);
        c5.setPre(c4);
        c4.setPre(c3);
        c3.setPre(c2);
        c2.setPre(c1);
        c1.setPre(c0);

        new Solution().lastRemaining(c0,5);
        System.out.println("--------------------");
        new Solution().lastRemaining(11 , 5 );
    }
}
